{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Magic Index LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMagicIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #魔术索引"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>魔术索引。 在数组<code>A[0...n-1]</code>中，有所谓的魔术索引，满足条件<code>A[i] = i</code>。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：nums = [0, 2, 3, 4, 5]\n",
    "<strong> 输出</strong>：0\n",
    "<strong> 说明</strong>: 0下标的元素为0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：nums = [1, 1, 1]\n",
    "<strong> 输出</strong>：1\n",
    "</pre>\n",
    "\n",
    "<p><strong>说明:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>nums长度在[1, 1000000]之间</li>\n",
    "\t<li>此题为原书中的 Follow-up，即数组中可能包含重复元素的版本</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [magic-index-lcci](https://leetcode.cn/problems/magic-index-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [magic-index-lcci](https://leetcode.cn/problems/magic-index-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i==nums[i]:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        # for i in range(len(nums)):\n",
    "        #     if i == nums[i]:\n",
    "        #         return i\n",
    "        #         break\n",
    "        # return -1\n",
    "        left, right = 0, len(nums) - 1\n",
    "        \n",
    "        while left <= right:\n",
    "            if nums[left] > left:\n",
    "                left = nums[left]\n",
    "            elif nums[left] == left:\n",
    "                return left\n",
    "            else:\n",
    "                left += 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        while k < len(nums):\n",
    "            if nums[k] == k:\n",
    "                return k\n",
    "            elif nums[k] > k:\n",
    "                k = nums[k]\n",
    "            else:\n",
    "                k += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i,num in enumerate(nums):\n",
    "            if i==num:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i==nums[i]:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        return next(iter(i for i,num in enumerate(nums) if i==num),-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        # 【有序数组】\n",
    "        if not nums:\n",
    "            return -1\n",
    "        if nums[0]==0:\n",
    "            return 0\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<=j:\n",
    "            if nums[i]>i:# 说明以nums[i]为下标的位置之前所有的数字都要大于其索引\n",
    "                i=nums[i] # 索引直接从索引位置nums[i]开始搜索，才有可能nums[i]==i\n",
    "            elif nums[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                i+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        while k < len(nums):\n",
    "            if nums[k] > k:\n",
    "                k = nums[k]\n",
    "            elif nums[k] < k:\n",
    "                k += 1\n",
    "            else:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findMagicIndex(self, nums: List[int]) -> int:\n",
    "\t\tfor i in range(len(nums)):\n",
    "\t\t\tif i == nums[i]:\n",
    "\t\t\t\treturn i\n",
    "\t\treturn -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        # for i in range(len(nums)):\n",
    "        #     if i==nums[i]:\n",
    "        #         return i\n",
    "        # return -1\n",
    "        i, n = 0, len(nums)\n",
    "        while i<n:\n",
    "            if i<nums[i]:\n",
    "                i = nums[i]\n",
    "            elif i==nums[i]:\n",
    "                return i\n",
    "            else:\n",
    "                i+=1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for index,item in enumerate( nums):\n",
    "            if index==item:\n",
    "                return item\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[0, 2, 3, 4, 5]\n",
    "[1, 1, 1]\n",
    "\n",
    "\n",
    "1 <= nums.length <= 1^6\n",
    "This problem is the follow-up of the original problem in the book,\n",
    "i.e. the values are not distinct.\n",
    "\n",
    "Array, Binary Search\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        return self.bisect(nums, 0, len(nums)-1)\n",
    "    def bisect(self, nums, l, r):\n",
    "        if l > r: return -1\n",
    "        m = l + ((r-l) >> 1)\n",
    "        left = self.bisect(nums, l, m-1)\n",
    "        if left != -1:\n",
    "            return left\n",
    "        if nums[m] == m:\n",
    "            return m\n",
    "        return self.bisect(nums, m+1, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for index,ele in enumerate(nums):\n",
    "            if index==ele:\n",
    "                return index\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i\n",
    "                break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for key, value in enumerate(nums):\n",
    "            if key == value:\n",
    "                return key\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        ans = -1\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                ans = i\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i, x in enumerate(nums):\n",
    "            if i == x:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == n: return i\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "            i += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if nums[-1] < 0 or nums[0] > n:\n",
    "            return -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        if nums[-1] < 0 or nums[0] > len(nums):\n",
    "            return -1\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        res = float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                res = min(res, i)\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i <= j:\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "            elif nums[i] > i:\n",
    "                i = nums[i]\n",
    "            else:\n",
    "                i += 1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i==nums[i]:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "            return next(iter(i for i,num in enumerate(nums) if i==num),-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        len1=len(nums)\n",
    "        for i in range(len1):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        while k < len(nums):\n",
    "            if nums[k] == k:\n",
    "                return k\n",
    "            elif nums[k] > k:\n",
    "                k = nums[k]\n",
    "            else:\n",
    "                k += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i,value in enumerate(nums):\n",
    "             if i == value:\n",
    "                 return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if i == nums[i]:\n",
    "                return i\n",
    "            i = max(nums[i], i+1)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            if i == num:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        index = 0\n",
    "        while index<len(nums):\n",
    "            if index == nums[index]:\n",
    "                return index\n",
    "            elif index<nums[index]:\n",
    "                index = nums[index]\n",
    "            else:\n",
    "                index += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        a=[]\n",
    "        for ans,c in enumerate(nums):\n",
    "            if ans==c:\n",
    "                a.append(ans)\n",
    "        if a:\n",
    "            return min(a)\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        '''for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i \n",
    "        return -1'''\n",
    "        l, r = 0, len(nums)\n",
    "        while l < r:\n",
    "            if nums[l] > l: # 如果nums[l] > l，则将l跳跃到nums[l]\n",
    "                l = nums[l]\n",
    "            elif nums[l] == l:\n",
    "                return l \n",
    "            else:\n",
    "                l += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for index, item in enumerate(nums):\n",
    "            if item==index:\n",
    "                return index\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        # 方法一：最简单的遍历（时间复杂度为O(N)）\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] == i:\n",
    "        #         return nums[i]\n",
    "        # return -1\n",
    "\n",
    "        # 方法二：优化后的遍历（能减少搜索时间，<O(N)）\n",
    "        startPoint = 0\n",
    "        endPoint = len(nums) - 1\n",
    "        while startPoint <= endPoint:\n",
    "            if nums[startPoint] > startPoint:\n",
    "                startPoint = nums[startPoint]\n",
    "            elif nums[startPoint] == startPoint:\n",
    "                return startPoint\n",
    "            else:\n",
    "                startPoint += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "         if nums[i]==i:\n",
    "            return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i,x in enumerate(nums):\n",
    "            if i==x:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        return self.find_magic_index(nums, 0, len(nums) - 1)\n",
    "\n",
    "    def find_magic_index(self, nums, left, right):\n",
    "        # 未找到的符合要求的返回-1\n",
    "        if left>right:\n",
    "            return -1\n",
    "        # 取中间元素\n",
    "        mid =left + (right - left) // 2\n",
    "\n",
    "        # 先看是否能找到第一个魔术索引，先往左侧找\n",
    "        left_ans = self.find_magic_index(nums, left, mid-1)\n",
    "\n",
    "        # 如果左侧存在，那么返回 left_ans\n",
    "        if left_ans != -1:\n",
    "            return left_ans\n",
    "        # 如果不存在，先比较 nums[mid] == mid\n",
    "        elif nums[mid] == mid:\n",
    "            return mid\n",
    "        # 不存在，且 nums[mid] != mid 时，往右侧寻找\n",
    "        return self.find_magic_index(nums, mid + 1, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i==nums[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                i = max(i+1,nums[i])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:                \n",
    "                return i\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i==nums[i]:\n",
    "                return i\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i,c in enumerate(nums):\n",
    "            if i==c:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==i:\n",
    "                return i\n",
    "                break\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for idx in range(len(nums)): \n",
    "            if idx == nums[idx]: \n",
    "                return idx \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                \n",
    "                return i\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        i=0\n",
    "        while i<len(nums):\n",
    "            if i==nums[i]:\n",
    "                return i\n",
    "            i=max(nums[i],i+1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        if nums[0] == 0:\n",
    "            return 0\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        while left < right:\n",
    "            if nums[left] > left:\n",
    "                left = nums[left]\n",
    "            elif nums[left]==left:\n",
    "                return left\n",
    "            else:\n",
    "                left += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:                \n",
    "                return i\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if i == nums[i]:\n",
    "                \n",
    "                return i\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        # if len(nums) == 0:\n",
    "        #     return -1\n",
    "        # mid = len(nums) // 2\n",
    "        # if nums[mid] == mid:\n",
    "        #     return nums[0]\n",
    "        # elif nums[mid] > mid:\n",
    "        #     return self.findMagicIndex(nums[:mid])\n",
    "        # else:\n",
    "        #     return self.findMagicIndex(nums[mid + 1:])\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == i:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        return next(iter(i for i,num in enumerate(nums) if i==num),-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        #   输入：nums = [0, 2, 2, 4, 5]\n",
    "        #  输出：0\n",
    "        #  说明: 0下标的元素为0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if i == num: return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 27/40 --pass  测例【0,0,2】error\n",
    "# class Solution:\n",
    "#     def findMagicIndex(self, nums: List[int]) -> int:\n",
    "#         n=len(nums)\n",
    "#         i,j=0,n-1\n",
    "#         ans=float(\"inf\")\n",
    "#         while i<j:\n",
    "#             mid=(i+j)//2\n",
    "#             if nums[mid]>=mid:\n",
    "#                 j=mid \n",
    "#                 if nums[mid]==mid:\n",
    "#                     ans=min(ans,mid)\n",
    "#             else:\n",
    "#                 i=mid+1\n",
    "#         if nums[i]==i:\n",
    "#             ans=min(ans,i)\n",
    "#         return ans if ans<float(\"inf\") else -1\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        # i,j=0,n-1\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if nums[i]>i:\n",
    "                i=nums[i]\n",
    "            elif nums[i]==i:\n",
    "                return i  \n",
    "            else:\n",
    "                i+=1\n",
    "        return -1\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMagicIndex(self, nums: List[int]) -> int:\n",
    "        if not nums: return -1\n",
    "        if nums[0]==0: return 0\n",
    "        p,n=0,len(nums)\n",
    "        while p<n:\n",
    "            if nums[p]>p: p=nums[p]\n",
    "            elif nums[p]==p: return p\n",
    "            else: p+=1\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
